package com.mango.data.structure.hash;

import java.util.*;

/**
 * HashMap实现
 * @Author: mango
 * @Date: 2022/5/21 10:53 上午
 * @Desc: 数组加链表
 */
public class HashMap<K,V> implements Map<K,V> {
    private Node<K,V>[] array;
    // 容量
    private int capacity;
    // 大小
    private int size;
    // 默认容量
    private int DEFAULT_CAPACITY = 8;
    // 负载因子
    private float LOAD_FACTOR = 0.75f;

    public HashMap(){
        this.size = 0;
    }
    // hash函数
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return getNode(hash(key), (K) key) != null ? true : false;
    }

    private Node<K,V> getNode(int hash,K key){
        int index = hash % capacity;
        if(array[index] == null){
            return null;
        }else{
            Node<K,V> node = array[index];
            while (node != null && !node.key.equals(key)){
                node = node.next;
            }
            if(node != null){
                return node;
            }
        }
        return null;
    }

    private Node<K,V> getNodeByVal(int hash,V val){
        int index = hash % capacity;
        if(array[index] == null){
            return null;
        }else{
            Node<K,V> node = array[index];
            while (node != null && !node.val.equals(val)){
                node = node.next;
            }
            if(node != null){
                return node;
            }
        }
        return null;
    }

    @Override
    public boolean containsValue(Object value) {
        return getNodeByVal(hash(value),(V)value) == null ? true : false;
    }

    @Override
    public V get(Object key) {
        if(containsKey(key)){
            return getNode(hash(key), (K) key).val;
        }
        return null;
    }
    // 扩容,缩容
    private void resize(int flag){
        int oldCapacity = capacity;
        Node<K,V>[] oldArray = this.array;
        if(flag == 1) {
            this.capacity = this.capacity << 1;
        }else{
            this.capacity = this.capacity >> 1;
        }
        this.array = new Node[capacity];
        this.size = 0;
        for(int i=0;i<oldCapacity;i++){
            Node<K, V> node = oldArray[i];
            if(node != null){
                putVal(node.key,node.val);
                while (node.next != null){
                    putVal(node.next.key,node.next.val);
                    node = node.next;
                }
            }
        }
    }
    private void resize(){
        int m = (int) (capacity * LOAD_FACTOR / 2);
        // 超过负载，则扩容
        if(size / capacity > LOAD_FACTOR){
            resize(1);
            System.out.println("扩容");
        }
        // 低于负载的一半，且缩减后的容量不小于默认容量，则缩容
        else if(size < m && m >= (DEFAULT_CAPACITY / 2) ){
            resize(0);
            System.out.println("缩容");
        }
    }
    @Override
    public V put(K key, V value) {
        // 如果为空，则先创建默认容量大小的数组
        if(array == null){
            this.array = new Node[DEFAULT_CAPACITY];
            this.capacity = DEFAULT_CAPACITY;
        }
        // 设置值
        putVal(key,value);
        // 容量控制
        resize();
        return value;
    }

    private void putVal(K key,V value){
        int index = hash(key) % capacity;
        Node<K,V> node = array[index];
        // 如果key已经存在，则替换value的值
        if(containsKey(key)){
            getNode(hash(key),key).val = value;
            return ;
        }
        // 不存在，则加入
        if(node == null){
            array[index] = new Node(key,value);
        }else{
            while (node.next != null){
                node = node.next;
            }
            node.next = new Node(key,value);
        }
        size++;
    }

    @Override
    public V remove(Object key) {
        if(containsKey(key)){
            int index = hash(key) % capacity;
            if(array[index] != null){
                Node<K,V> node = array[index];
                if(node.next == null){
                    array[index] = null;
                }else{
                    while (node.next != null && !node.next.key.equals(key)){
                        node = node.next;
                    }
                    node.next = node.next.next;
                }
                size--;
                // 容量控制
                resize();
            }
        }
        return null;
    }


    @Override
    public void putAll(Map m) {
        for(Object k : m.keySet()){
            K key = (K) k;
            putVal(key, (V) m.get(k));
        }
    }

    @Override
    public void clear() {
        this.size = 0;
        this.capacity = 0;
        this.array = null;
    }

    @Override
    public Set<K> keySet() {
        HashSet set = new HashSet();
        for(int i=0;i<capacity;i++){
            Node<K, V> node = this.array[i];
            if(node != null){
                set.add(node.key);
                while (node.next != null){
                    set.add(node.next.key);
                    node = node.next;
                }
            }
        }
        return set;
    }

    @Override
    public Collection values() {
        List<V> result = new ArrayList<>();
        for(int i=0;i<capacity;i++){
            Node<K, V> node = this.array[i];
            if(node != null){
                result.add(node.val);
                while (node.next != null){
                    result.add(node.next.val);
                    node = node.next;
                }
            }
        }
        return result;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        HashSet<Entry<K,V>> set = new HashSet();
        for(int i=0;i<capacity;i++){
            Node<K, V> node = this.array[i];
            if(node != null){
                set.add(node);
                while (node.next != null){
                    set.add(node.next);
                    node = node.next;
                }
            }
        }
        return set;
    }


    /**
     * 链表节点
     */
    final class Node<K,V> implements Entry<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.val = val;
            this.key = key;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    ", next=" + next +
                    '}';
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return val;
        }

        @Override
        public V setValue(V value) {
            this.val = value;
            return value;
        }
    }

    @Override
    public String toString() {
        return "HashMap{" +
                "array=" + Arrays.toString(array) +
                ", capacity=" + capacity +
                ", size=" + size +
                '}';
    }
}
